#include"BstTree.h"

template<typename T>
BstTree<T>::BstTree()
	:cursize(0)
{
	head = head->BuyNode();
}

template<typename T>
BstTree<T>::~BstTree()
{
	BstNode<T>* p = head->left;
	while (p != nullptr)
	{
		Delete(p->key);
		p = head->left;
	}
	head->FreeNode(head);
}

template<typename T>
void BstTree<T>::InOrder()
{
	if (IsEmpty()) return;
	_InOrder(head->parent);
	std::cout << std::endl;
}
template<typename T>
void BstTree<T>::_InOrder(BstNode<T>* root)
{
	if (nullptr == root) return;
	else
	{
		_InOrder(root->left);
		std::cout << root->key << " ";
		_InOrder(root->right);
	}
}

//三叉链表 中序遍历的下一个节点
template<typename T>
BstNode<T>* BstTree<T>::NextNode(BstNode<T>* node)
{
	if (nullptr == node) return nullptr;
	if (node->right != nullptr)
	{
		node = node->right;
		while (node->left != nullptr)
		{
			node = node->left;
		}
		return node;
	}
	while (node->parent != head)
	{
		BstNode<T>* pa = node->parent;
		if (pa->left == node) return pa;
		node = node->parent;
	}
	return nullptr;
}
template<typename T>
void BstTree<T>::NoRecInOrder()
{
	if (IsEmpty()) return;
	BstNode<T>* p = head->left;
	while (p != nullptr)
	{
		std::cout << p->key << " ";
		p = NextNode(p);
	}
	std::cout << std::endl;
}

template<typename T>
BstNode<T>* BstTree<T>::PreNode(BstNode<T>* node)
{
	if (nullptr == node) return node;
	if (node->left != nullptr)
	{
		node = node->left;
		while (node->right != nullptr)
		{
			node = node->right;
		}
		return node;
	}
	while (node->parent != head)
	{
		BstNode<T>* pa = node->parent;
		if (pa->right == node) return pa;
		node = node->parent;
	}
	return nullptr;
}
template<typename T>
void BstTree<T>::MirrorNoRecInOrder()
{
	if (IsEmpty()) return;
	BstNode<T>* p = head->right;
	while (p != nullptr)
	{
		std::cout << p->key << " ";
		p = PreNode(p);
	}
	std::cout << std::endl;
}

template<typename T>
bool BstTree<T>::Insert(const T& val)
{
	if (nullptr == head->parent)
	{
		head->parent = head->BuyNode(val);
		head->left = head->parent;
		head->right = head->parent;
		head->parent->parent = head;
	}
	else
	{
		BstNode<T>* pa = head;
		BstNode<T>* p = pa->parent;
		while (nullptr != p && p->key != val)
		{
			pa = p;
			p = val > p->key ? p->right : p->left;
		}
		if (p != nullptr && p->key == val) return false;
		p = p->BuyNode(val);
		p->parent = pa;
		val > pa->key ? pa->right = p : pa->left = p;
		if (head->left->key > val)
		{
			head->left = p;
		}
		if (head->right->key < val)
		{
			head->right = p;
		}
	}
	
	++cursize;
	return true;
}

template<typename T>
bool BstTree<T>::Delete(const T& val)
{
	if (IsEmpty()) return false;
	BstNode<T>* p = NoRecFindValue(val);
	if (nullptr == p) return false;

	if (p == head->left) head->left = NextNode(p);
	if (p == head->right) head->right = PreNode(p);

	if (p->left != nullptr && p->right != nullptr)
	{
		BstNode<T>* pnext = NextNode(p);
		p->key = pnext->key;
		p = pnext;
	}
	BstNode<T>* pa = p->parent;
	BstNode<T>* child = p->left != nullptr ? p->left : p->right;
	if (child != nullptr) child->parent = pa;
	if (pa == head) head->parent = child;
	else
	{
		if (pa->left == p) pa->left = child;
		else pa->right = child;
	}
	p->FreeNode(p);
	cursize--;
	return true;
}

template<typename T>
BstNode<T>* BstTree<T>::FindValue(const T& val)
{
	if (IsEmpty()) return nullptr;
	return _FindValue(head->parent, val);
}
template<typename T>
BstNode<T>* BstTree<T>::_FindValue(BstNode<T>* root, const T& val)
{
	if (nullptr == root || val == root->key) return root;
	else if (val < root->key) return  _FindValue(root->left, val);
	else return _FindValue(root->right, val);
}

template<typename T>
BstNode<T>* BstTree<T>::NoRecFindValue(const T& val)
{
	if (IsEmpty()) return nullptr;
	BstNode<T>* p = head->parent;
	while (p != nullptr && val != p->key)
	{
		p = val > p->key ? p->right : p->left;
	}
	return p;
}

template<typename T>
int BstTree<T>::GetSize()
{
	return cursize;
}

template<typename T>
bool BstTree<T>::IsEmpty()
{
	return nullptr == head->parent;
}